package algorithm;

public class leetcode_0516 {
    public int longestPalindromeSubseq(String s) {
        int len=s.length();
        if(len==1) return 1;
        int [][] dp=new int[len][len];
        for(int i=0;i<len-1;++i){
            dp[i][i]=1;
            if(s.charAt(i)==s.charAt(i+1)){
                dp[i][i+1]=2;
            }
            else dp[i][i+1]=1;
        }
        dp[len-1][len-1]=1;
        for(int j=2;j<len;++j){
            for(int i=0;i+j<len;++i){
                if(s.charAt(i)==s.charAt(i+j)){
                    dp[i][i+j]=max(dp[i+1][i+j-1]+2,dp[i+1][j+i],dp[i][i+j-1]);
                }
                else{
                    dp[i][i+j]=max(dp[i+1][i+j-1],dp[i+1][j+i],dp[i][i+j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
    public int max(int a,int b,int c){
        if(a>b){
            return (a>c)?a:c;
        }
        else{
            return (b>c)?b:c;
        }
    }
}
